/**
 * 210824：升级修改【three.js r120-r131】
 * 20220304:[require] to [import]...jordia
 */
import {Triangle,Vector2,Matrix4,Quaternion,Vector3,Object3D,BufferGeometry,Line,LineBasicMaterial,BufferAttribute,Color,MeshStandardMaterial,Mesh,PlaneGeometry,Box3} from 'three';

const DEFAULT_UP=new Vector3(0,1,0);
const DEFAULT_LEFT=new Vector3(1,0,0);
const DEFAULT_FRONT=new Vector3(0,0,1);
const UNIT=1;

/**
 * 单位化数字
 * @param number
 * @param direction
 * @param normal
 * @returns {number}
 */
const normalizeNumber=(number,direction,normal=0.02)=>{
    let decN=normal;
    if(direction>0){
        return Math.ceil(number/decN)*decN;
    }else{
        return Math.floor(number/decN)*decN;
    }
};

/**
 * 单位化向量到y平面
 * @param vec
 * @param direction
 * @param unit
 */
const normalizeUV=(vec,direction,unit)=>{
    vec.x=Number.parseFloat(normalizeNumber(vec.x,direction,unit));
    vec.y=0;
    vec.z=Number.parseFloat(normalizeNumber(vec.z,direction,unit));
};

/**
 * Y平面矩形有界箱
 * 给定起点和终点，沿线段方向以extent为宽度构建有向有界箱
 * 矩阵变换将改变箱体方向及长度，但不影响其宽度
 * 当起点和终点的投影长度小于extent*2时则代表一个长为extent*2的正方形区域
 */
class Obb{
    constructor(start,end,extent){
        this._start=new Vector3().copy(start)||new Vector3(0,0,0);
        this._end=new Vector3().copy(end)||new Vector3(1,0,0);
        this._extent=extent||1;
        this.init();
    }

    /**
     * 获取uv最小的角点
     * @returns {null|this}
     */
    get iuiv(){
        this._iuiv.y=0;
        return this._iuiv;
    }

    /**
     * 获取u最小v最大的角点
     * @returns {null|this}
     */
    get iuav(){
        this._iuav.y=0;
        return this._iuav;
    }

    /**
     * 获取u最大v最小的角点
     * @returns {null|this}
     */
    get auiv(){
        this._auiv.y=0;
        return this._auiv;
    }

    /**
     * 获取uv最大的角点
     * @returns {null|this}
     */
    get auav(){
        this._auav.y=0;
        return this._auav;
    }

    /**
     * 矩阵变换
     * @param mat4
     * @returns {Obb}
     */
    applyMatrix4(mat4){
        this._start.applyMatrix4(mat4);
        this._end.applyMatrix4(mat4);
        this._extent*=mat4.getMaxScaleOnAxis();
        this.initialize();
        return this;
    }

    /**
     * 克隆
     * @returns {Obb}
     */
    clone(){
        return new Obb(this._start,this._end,this._extent);
    }

    /**
     * 销毁
     */
    dispose(){
        this._start=null;
        this._end=null;
        this._extent=null;
        this._dV=null;
        this._dU=null;
        this._iuiv=null;
        this._iuav=null;
        this._auiv=null;
        this._auav=null;
        this._tV0=null;
        this._tV1=null;
    }

    /**
     * 初始化
     * @private
     */
    init(){
        this.initVariable();
        this.initialize();
    }

    /**
     * 初始化变量
     * @private
     */
    initVariable() {
        this._tV0 = new Vector3();
        this._tV1 = new Vector3();
        this._dU = new Vector3();
        this._dV = new Vector3();
        this._iuiv = new Vector3();
        this._iuav = new Vector3();
        this._auiv = new Vector3();
        this._auav = new Vector3();
    }

    /**
     * 初始化状态
     * @private
     */
    initialize(){
        this._tV0.copy(this._start).y=0;
        this._tV1.copy(this._end).y=0;
        let dsq=this._tV0.distanceToSquared(this._tV1);
        let ext=this._extent*2;
        if(dsq<=ext*ext){
            this._tV0.addVectors(this._start,this._end).multiplyScalar(0.5);
            this._dU.copy(DEFAULT_LEFT).multiplyScalar(this._extent);
            this._dV.copy(DEFAULT_FRONT).multiplyScalar(this._extent);
            let ax=Math.max(this._dU.x,this._dV.x);
            let az=Math.max(this._dU.z,this._dV.z);
            this._iuiv.set(this._tV0.x-ax,this._tV0.y,this._tV0.z-az);
            this._iuav.set(this._tV0.x-ax,this._tV0.y,this._tV0.z+az);
            this._auiv.set(this._tV0.x+ax,this._tV0.y,this._tV0.z-az);
            this._auav.set(this._tV0.x+ax,this._tV0.y,this._tV0.z+az);
        }else{
            this._dV.subVectors(this._end,this._start);
            this._dU.crossVectors(this._dV,DEFAULT_UP).normalize().multiplyScalar(this._extent);
            this._iuiv.copy(this._start).sub(this._dU);
            this._iuav.copy(this._start).add(this._dU);
            this._auiv.copy(this._end).sub(this._dU);
            this._auav.copy(this._end).add(this._dU);
        }
    }
}

/**
 * 单元格放置区
 * 1.为避免精度问题，单元格单位为1，不对外暴露
 *      要设置放置区大小请对放置区实例进行缩放或平移并更新
 * 2.输入信息中的变换矩阵一般为对象的变换矩阵，此矩阵将用于把
 *      设置的OBB从对象空间变换到世界空间，也可以是计算得到的与对象无关的矩阵
 * 3.对象放置完毕后，如需要对其进行任何变换，都请先从放置区移除，
 *      变换完成再添加进放置区
 * 4.单元格数量不要太多太密，单元格数量为：u*v*4（横向尺寸u,纵向尺寸v）,
 *      放置密集时单元格太多会大大增加查询的次数
 * 5.使用createObb来创建放置信息的obb列表，如下：
 *      gridGround.addItem(
 *              object.uuid,
 *              object.matrixWorld,
 *              object.position,
 *              gridGround.createObb( new Vector3(-1,0,0), new Vector3(1,0,0), 0.2),
 *              gridGround.createObb( new Vector3(1,0,0),  new Vector3(1,0,1), 0.2)
 *      );
 *      其中参数start和end为对象局部空间并正常进行矩阵变换，extent根据变换的最大缩放进行缩放，
 *      当start和end的y平面投影距离小于extent*2时，obb范围是以extent为半长的正方形
 */
export default class GridGround extends Object3D{
    constructor(){
        super();
        this.init();
    }

    //-----------------------------------------对外属性及方法--------------------------------------------------------

    /**
     * 设置没有找到足够的空闲区域时的回调函数
     * @param func {function}
     */
    set onError(func){
        this._errorCall=func;
    }

    /**
     * 打开或关闭调试（只显示当前状态的调试，不是动态的）
     * @param bol {boolean}
     */
    set debug(bol){
        if(bol){
            this.debug=false;
            this.getVerts();

            // 20210824
            // let g=new Geometry();
            // g.vertices=this._verts;
            let g=new BufferGeometry();
            let ps=new Float32Array(this._verts.length*3);
            for(let i=0;i<this._verts.length;i++){
                ps[i*3]=this._verts[i].x;
                ps[i*3+1]=this._verts[i].y;
                ps[i*3+2]=this._verts[i].z;
            }
            g.setAttribute('position',new BufferAttribute(ps,3));

            this._debug=new Object3D();
            this._debug.add(new Line(g,new LineBasicMaterial({color:new Color(1,0,0)})));
            let m=new MeshStandardMaterial({color:new Color(0,1,0),transparent:true,opacity:0.4});
            for(let i=0;i<this._nU*2;i++){
                for(let j=0;j<this._nV*2;j++){
                    if(this._aC[i*this._nV*2+j]>0){
                        let g=new PlaneGeometry(UNIT,UNIT);
                        let mm=new Mesh(g,m);
                        this._debug.add(mm);
                        mm.rotation.x=-Math.PI*0.5;
                        mm.position.set((i-this._nU)*UNIT+UNIT*0.5,0,(j-this._nV)*UNIT+UNIT*0.5);
                    }
                }
            }
            this.add(this._debug);
        }else{
            if(!this._debug)return;
            this.remove(this._debug);
            for(let child of this._debug.children){
                child.geometry.dispose();
                child.material.dispose();
            }
            this._debug=null;
        }
    }

    /**
     * 设置放置区横向和纵向的尺寸并重设所有放置
     * @param u {int} 横向尺寸（横向总数的一半）
     * @param v {int} 纵向尺寸（纵向总数的一半）
     */
    setGrids(u,v){
        this._nU=Math.round(u);
        this._nV=Math.round(v);
        this._aC=new Uint8Array(this._nU*this._nV*4);
        this._iC=new Uint16Array(this._nU*this._nV*4);
        this.update();
    }

    /**
     * 检测并获取目标的可放置区域（输出box3序列）
     * @param transform {Matrix4} 用于变换OBB的矩阵（一般为对象的变换矩阵，注意对象的矩阵是否及时更新）
     * @param out {array} 输出序列（box3在y平面上投影的序列）
     * @param obb {...Obb} 确定目标占用区的包围盒
     */
    checkItem(transform,out,...obb){
        //only Check to get valid zone
        out.length=0;
        this.setExtents(obb,transform);
        this.transformBound();
        this.setUVRange();
        if(this.checkRange()){
            this.setBlocks();
            for(let block of this._blocks){
                if(!block)break;
                let box=block[0];
                let isInt=false;

                for(let i=0;i<this._auiv.length;i++){
                    if(this.boxIntersectObb(box,this._iuiv[i],this._iuav[i],this._auav[i],this._auiv[i])){
                        isInt=true;
                        break;
                    }
                }

                if(isInt){
                    out.push(box.applyMatrix4(this.matrixWorld));
                }
            }
        }else{
            this.expandOriginalBound();
            this.createVirtualBlocks();
            this.removeRedundancyBlock();
            if(this.getClosestOffset()) {
                for(let block of this._blocks){
                    if(!block)break;
                    let box=block[0];
                    let ox=this._offset.x*UNIT;
                    let oz=this._offset.y*UNIT;
                    box.min.x+=ox;
                    box.min.z+=oz;
                    box.max.x+=ox;
                    box.max.z+=oz;
                    out.push(box.applyMatrix4(this.matrixWorld));
                }
            }
        }
    }

    /**
     * 创建2D有向有界箱（以一条线段及宽度构建，类似胶囊体的构建）
     * @param start {Vector3} 箱体的起始段
     * @param end {Vector3} 箱体的终端
     * @param extent {number} 箱体的宽度（不受变换影响）
     * @returns {Obb}
     */
    createObb(start,end,extent){
        return new Obb(start,end,extent);
    }

    /**
     * 添加放置信息并输出放置位置
     * @param uuid {string} 放置对象的唯一ID
     * @param transform {Matrix4} 用于变换OBB的矩阵（一般为对象的变换矩阵，注意对象的矩阵是否及时更新）
     * @param out {Vector3} 输出放置位置（世界）
     * @param obb {...Obb} 确定目标占用区的包围盒
     */
    addItem(uuid,transform,out,...obb){
        for(let item of this._items){
            if(item[0]===uuid)return;
        }
        let index=this._items.length+1;
        let itm=[uuid,index,transform,obb,out];
        let obbc=[];
        for(let ob of obb){
            obbc.push(ob.clone());
        }
        let itmc=[uuid,index,transform,obbc,out];
        this._curItem=itm;
        this._items.push(itm);
        this._recordItems.push(itmc);
        this.location(transform,out,obb);
    }

    /**
     * 获取有界箱在给定变换下直接投影后有交叠的ID,并返回是否超界
     * @param transform {Matrix4} 用于变换OBB的矩阵
     * @param out {Array} 输出交叠ID序列
     * @param obb {Obb} 确定占用区域的包围盒
     * @returns {boolean} 是否超出范围
     */
    overlaps(transform,out,...obb) {
        out.length = 0;
        this.setExtents(obb, transform);
        this.transformBound();
        this.setUVRange();
        /**
         * checkRange方法的变体（区分超出范围，交叠，二者）
         */
        let outOfRange = false;
        let overlap = false;
        for (let k = 0; k < this._rangeU.length; k++) {
            let ru = this._rangeU[k];
            let rv = this._rangeV[k];
            if (ru[0] < 0 || ru[1] < 0 || rv[0] < 0 || rv[1] < 0) outOfRange = true;

            for (let i = ru[0]; i <= ru[1]; i++) {
                for (let j = rv[0]; j <= rv[1]; j++) {
                    if (this._aC[i * this._nV * 2 + j]) overlap = true;
                }
            }
        }
        if (!outOfRange && !overlap) return outOfRange;
        /**
         * 查询交叠ID
         */
        this.expandOriginalBound();
        this.createVirtualBlocks();
        this.removeRedundancyBlock();
        for(let block of this._blocks){
            if(!block)break;
            let u=block[1],v=block[2];
            if(u<0||v<0)continue;
            let idx=u*this._nV*2+v;
            if(this._aC[idx]){
                let iIdx=this._iC[idx];
                let uuid=this._items[iIdx-1][0];
                if(out.indexOf(uuid)<0) out.push(uuid);
            }
        }
        return outOfRange;
    }

    /**
     * 移除放置信息
     * @param uuid
     */
    removeItem(uuid){
        for(let i=0;i<this._items.length;i++){
            if(this._items[i][0]===uuid){
                let item=this._items[i];
                let idx=item[1];
                for(let j=0;j<this._iC.length;j++){
                    if(this._iC[j]===idx){
                        this._aC[j]=0;
                        this._iC[j]=0;
                    }else if(this._iC[j]>idx){
                        this._iC[j]--;
                    }
                }
                this._items.splice(i,1);
                this._recordItems.splice(i,1);
                for(let k=0;k<this._items.length;k++){
                    if(this._items[k][1]>idx){
                        this._items[k][1]--;
                        this._recordItems[k][1]--;
                    }
                }
                return;
            }
        }
    }

    /**
     * 清除放置信息
     */
    clearItem(){
        for(let i=0;i<this._iC.length;i++) {
            this._aC[i] = 0;
            this._iC[i] = 0;
        }
        this._items.length=0;
        this._recordItems.length=0;
        this._oBound[0]=null;
        this._rBound[0]=null;
        this._blocks[0]=null;
    }

    /**
     * 更新并重设所有放置（矩阵变换后需调用）
     */
    update(){
        this.updateMatrixWorld();
        let debug=this._debug!==null;
        this.debug=false;
        let items=[...this._recordItems];
        this.clearItem();
        for(let item of items){
            this.addItem(item[0],item[2],item[4],...item[3]);
        }
        this.debug=debug;
    }

    /**
     * 销毁
     */
    dispose(){
        this.debug=false;
        this.clearItem();
        this._items=null;
        this._recordItems=null;
        this._posOffset=null;
        this._nU=null;
        this._nV=null;
        this._debug=null;
        this._verts=null;
        this._blocks=null;
        this._curItem=null;
        this._aC=null;
        this._iC=null;
        this._inv=null;
        this._oBound=null;
        this._rBound=null;
        this._tV0=null;
        this._tV1=null;
        this._tV2=null;
        this._tQ0=null;
        this._iuav=null;
        this._iuiv=null;
        this._auav=null;
        this._auiv=null;
        this._rangeU=null;
        this._rangeV=null;
        this._tT0=null;
        this._offset=null;
        this._errorCall=null;
    }

    //-----------------------------------------私有属性及方法-----------------------------------------------------------------

    /**
     * 定位并输出
     * @param transform
     * @param out
     * @param boxes
     */
    location(transform,out,boxes){
        this.setExtents(boxes,transform);
        this.transformBound();
        this.setUVRange();
        if (this.checkRange()) {
            this.setBlocks();
            this.markCeil();
            this.setForCurrentPosition(out);
        } else {
            this.expandOriginalBound();
            this.createVirtualBlocks();
            this.removeRedundancyBlock();
            if (this.getClosestOffset()) {
                this.markCeil();
                this.setForClosestOffset(out);
            } else {
                if (this._errorCall) this._errorCall();
            }
        }
    }

    /**
     * 根据偏移设置输出
     * @param out
     * @private
     */
    setForClosestOffset(out){
        let b=new Box3();
        for(let bound of this._rBound){
            if(!bound)break;
            b.union(bound);
        }
        b.getCenter(this._tV0);
        this._tV0.x+=this._offset.x*UNIT;
        this._tV0.z+=this._offset.y*UNIT;
        this._tV0.sub(this._posOffset);
        this._tV0.applyMatrix4(this.matrixWorld);
        out.copy(this._tV0);
    }

    /**
     * 检测偏移后的放置块是否可用
     * @param uOffset
     * @param vOffset
     * @returns {boolean}
     * @private
     */
    checkBlocks(uOffset,vOffset){
        for(let block of this._blocks){
            if(!block)break;
            let u=block[1]+uOffset;
            let v=block[2]+vOffset;
            if((u<0||u>=this._nU*2)||(v<0||v>=this._nV*2)){
                return false;
            }
            if(this._aC[u*this._nV*2+v]){
                return false;
            }
        }
        return true;
    }

    /**
     * 获取最近偏移
     * @returns {boolean}
     * @private
     */
    getClosestOffset(){
        let full=Math.max(this._nU*2,this._nV*2)+2;

        let ui=0,ua=this._nU*2,vi=0,va=this._nV*2;
        let dui=ui,dua=ua,dvi=vi,dva=va;
        for(let b of this._blocks){
            if(b===null)break;
            if(b[1]<dui)dui=b[1];
            if(b[1]>dua)dua=b[1];
            if(b[2]<dvi)dvi=b[2];
            if(b[2]>dva)dva=b[2];
        }
        let rangeOffset=Math.max(ui-dui,dua-ua,vi-dvi,dva-va);

        full=Math.max(full,rangeOffset*rangeOffset);
        let offset=rangeOffset-1;
        let reu=null,rev=null;
        do{
            offset++;
            let valid=true;

            for(let i=0;i<=offset;i++){
                valid=this.checkBlocks(i,offset);
                if(valid){
                    reu=i;
                    rev=offset;
                    break;
                }
                valid=this.checkBlocks(i,-offset);
                if(valid){
                    reu=i;
                    rev=-offset;
                    break;
                }
                valid=this.checkBlocks(offset,i);
                if(valid) {
                    reu = offset;
                    rev = i;
                    break;
                }
                valid=this.checkBlocks(-offset,i);
                if(valid){
                    reu=-offset;
                    rev=i;
                    break;
                }
                if(i===0)continue;
                valid=this.checkBlocks(-i,offset);
                if(valid){
                    reu=-i;
                    rev=offset;
                    break;
                }
                valid=this.checkBlocks(-i,-offset);
                if(valid){
                    reu=-i;
                    rev=-offset;
                    break;
                }
                valid=this.checkBlocks(offset,-i);
                if(valid) {
                    reu = offset;
                    rev = -i;
                    break;
                }
                valid=this.checkBlocks(-offset,-i);
                if(valid){
                    reu=-offset;
                    rev=-i;
                    break;
                }
            }
            if(valid)break;
        }while (offset<full);
        if(reu===null||rev===null)return false;
        for(let block of this._blocks){
            if(!block)break;
            block[1]+=reu;
            block[2]+=rev;
        }
        this._offset.set(reu,rev);
        return true;
    }

    /**
     * 移除冗余放置块
     * @private
     */
    removeRedundancyBlock() {
        for (let i = 0; i < this._blocks.length; i++) {
            if(!this._blocks[i])break;
            let box = this._blocks[i][0];

            let isInt = false;
            for (let k = 0; k < this._iuiv.length; k++) {
                if (this.boxIntersectObb(box, this._iuiv[k], this._iuav[k], this._auav[k], this._auiv[k])) {
                    isInt = true;
                    break;
                }
            }

            if (!isInt) {
                this._blocks.splice(i, 1);
                i--;
            }
        }
    }

    /**
     * 创建原始放置块
     * @private
     */
    createVirtualBlocks(){
        let c=0;
        for(let i=0;i<this._oBound.length;i++) {
            if(!this._oBound[i])break;
            let _oBound=this._oBound[i];
            let min = _oBound.min;
            let max = _oBound.max;
            for (let u = min.x; u < max.x; u += UNIT) {
                for (let v = min.z; v < max.z; v += UNIT) {
                    if(!this._blocks[c]) {
                        let b = new Box3();
                        b.min.set(u, 0, v);
                        b.max.set(u + UNIT, 0, v + UNIT);
                        this._blocks[c]=([b, u / UNIT + this._nU, v / UNIT + this._nV]);
                    }else{
                        this._blocks[c][0].min.set(u, 0, v);
                        this._blocks[c][0].max.set(u + UNIT, 0, v + UNIT);
                        this._blocks[c][1]= u / UNIT + this._nU;
                        this._blocks[c][2]=  v / UNIT + this._nV;
                    }
                    c++
                }
            }
        }
        this._blocks[c]=null;
    }

    /**
     * 扩展原始包围区
     * @private
     */
    expandOriginalBound(){
        let i=0;
        for(i=0;i<this._oBound.length;i++) {
            if(!this._oBound[i])break;
            if(!this._rBound[i]) {
                this._rBound[i] = new Box3().copy(this._oBound[i]);
            }else{
                this._rBound[i].copy(this._oBound[i]);
            }
            normalizeUV(this._oBound[i].min, -1, UNIT);
            normalizeUV(this._oBound[i].max, 1, UNIT);
        }
        this._rBound[i]=null;
    }

    /**
     * 标记单元格
     * @private
     */
    markCeil(){
        for(let block of this._blocks){
            if(!block)break;
            let box=block[0];
            let u=block[1];
            let v=block[2];
            let isInt=false;

            for(let i=0;i<this._iuiv.length;i++){
                if(this.boxIntersectObb(box,this._iuiv[i],this._iuav[i],this._auav[i],this._auiv[i])){
                    isInt=true;
                    break;
                }
            }

            if(isInt){
                this.activeCeil(u,v,false);
            }
        }
    }

    /**
     * 轴对齐盒与有向盒是否相交
     * @param box
     * @param obA
     * @param obB
     * @param obC
     * @param obD
     * @returns {boolean}
     * @private
     */
    boxIntersectObb(box,obA,obB,obC,obD){
        this._tT0.set(obA,obB,obC);
        if(box.intersectsTriangle(this._tT0))return true;
        this._tT0.set(obC,obD,obA);
        return box.intersectsTriangle(this._tT0);
    }

    /**
     * 设置放置块
     * @private
     */
    setBlocks(){
        let c=0;
        for(let k=0;k<this._rangeU.length;k++) {
            let ru=this._rangeU[k];
            let rv=this._rangeV[k];
            for (let i = ru[0]; i <= ru[1] - 1; i++) {
                let iu = (i - this._nU) * UNIT;
                let au = (i + 1 - this._nV) * UNIT;
                for (let j = rv[0]; j <= rv[1] - 1; j++) {
                    let iv = (j - this._nV) * UNIT;
                    let av = (j + 1 - this._nV) * UNIT;
                    if(!this._blocks[c]) {
                        let b = new Box3();
                        b.min.set(iu, 0, iv);
                        b.max.set(au, 0, av);
                        this._blocks[c]=[b,i,j];
                    }else{
                        this._blocks[c][0].min.set(iu, 0, iv);
                        this._blocks[c][0].max.set(au, 0, av);
                        this._blocks[c][1]=i;
                        this._blocks[c][2]=j;
                    }
                    c++;
                }
            }
        }
        this._blocks[c]=null;
    }

    /**
     * 启用/禁用单元格
     * @param iu
     * @param iv
     * @param bol
     * @private
     */
    activeCeil(iu,iv,bol) {
        let idx=iu*this._nV*2+iv;
        this._aC[idx]=bol?0:1;
        this._iC[idx]=bol?0:this._curItem[1];
    }

    /**
     * 使用当前信息设置输出
     * @param out
     * @private
     */
    setForCurrentPosition(out){
        let b=new Box3();
        for(let bound of this._oBound){
            if(!bound)break;
            b.union(bound);
        }
        b.getCenter(this._tV0);
        this._tV0.sub(this._posOffset);
        this._tV0.applyMatrix4(this.matrixWorld);
        out.copy(this._tV0);
    }

    /**
     * 检测UV范围是否合法
     * @returns {boolean}
     * @private
     */
    checkRange(){
        for(let k=0;k<this._rangeU.length;k++) {
            let ru=this._rangeU[k];
            let rv=this._rangeV[k];
            if (ru[0] < 0||ru[1] < 0||rv[0] < 0||rv[1] < 0) return false;

            for (let i = ru[0]; i <= ru[1]; i++) {
                for (let j = rv[0]; j <= rv[1]; j++) {
                    if (this._aC[i * this._nV * 2 + j]) return false;
                }
            }
        }
        return true;
    }

    /**
     * 设置UV范围
     * @private
     */
    setUVRange(){
        this._rangeU.length=0;
        this._rangeV.length=0;
        for(let i=0;i<this._oBound.length;i++) {
            if(!this._oBound[i])break;
            let ui = this._oBound[i].min.x;
            let ua = this._oBound[i].max.x;
            let vi = this._oBound[i].min.z;
            let va = this._oBound[i].max.z;
            this._rangeU[i] = [];
            this.getRange(ui, ua, this._nU, this._rangeU[i]);
            this._rangeV[i] = [];
            this.getRange(vi, va, this._nV, this._rangeV[i]);
        }
    }

    /**
     * 获取单元格范围
     * @param min
     * @param max
     * @param scale
     * @param rangeOut
     * @private
     */
    getRange(min,max,scale,rangeOut){
        rangeOut[0]=-1;
        rangeOut[1]=-1;
        for(let i=-scale;i<=scale;i++){
            let cu=i*UNIT;
            if(min>=cu)rangeOut[0]=i+scale;
            if(max>=cu)rangeOut[1]=i+scale+1;
        }
        rangeOut[1]=rangeOut[1]>scale*2?-1:rangeOut[1];
    }

    /**
     * 设置有向盒
     * @param boxes {array}
     * @param transform {Matrix4}
     * @private
     */
    setExtents(boxes,transform){
        // this._inv.getInverse(this.matrixWorld);20210824
        this._inv.copy(this.matrixWorld).invert();
        this._iuav.length = 0;
        this._iuiv.length = 0;
        this._auav.length = 0;
        this._auiv.length = 0;

        transform.decompose(this._tV0,this._tQ0,this._tV1);
        this._tV0.applyMatrix4(this._inv);
        this._tV0.y=0;
        let vs=[];

        for(let box of boxes) {
            box.applyMatrix4(transform).applyMatrix4(this._inv);
            this._iuiv.push(box.iuiv);
            this._iuav.push(box.iuav);
            this._auiv.push(box.auiv);
            this._auav.push(box.auav);
            vs.push(box.iuiv,box.iuav,box.auiv,box.auav);
        }
        let b=new Box3();
        b.setFromPoints(vs);
        b.getCenter(this._posOffset);
        this._posOffset.sub(this._tV0);
    }

    /**
     * 变换有向盒
     * @private
     */
    transformBound(){
        let i=0;
        for(i=0;i<this._auiv.length;i++) {
            if(!this._oBound[i]){
                this._oBound[i]=new Box3().setFromPoints([this._auiv[i], this._auav[i], this._iuiv[i], this._iuav[i]]);
            }else{
                this._oBound[i].setFromPoints([this._auiv[i], this._auav[i], this._iuiv[i], this._iuav[i]]);
            }
        }
        this._oBound[i]=null;
    }

    /**
     * 初始化
     * @private
     */
    init(){
        this.initVariable();
    }

    /**
     * 初始化变量
     * @private
     */
    initVariable(){
        this._items=[];
        this._recordItems=[];
        this._posOffset=new Vector3();
        this._nU=10;
        this._nV=10;
        this._debug=null;
        this._verts=[];
        this._blocks=[];//break value:null
        this._curItem=null;
        this._aC=new Uint8Array(this._nU*this._nV*4);//0:valid,1:invalid，位置(u,v)=u*2*nv+v
        this._iC=new Uint16Array(this._nU*this._nV*4);//0:null,res:index
        this._inv=new Matrix4();
        this._oBound=[];//break value:null
        this._rBound=[];//break value:null
        this._tV0=new Vector3();
        this._tV1=new Vector3();
        this._tV2=new Vector3();
        this._tQ0=new Quaternion();
        this._iuav=[];
        this._iuiv=[];
        this._auav=[];
        this._auiv=[];
        this._rangeU=[];
        this._rangeV=[];
        this._tT0=new Triangle();
        this._offset=new Vector2();
        this._errorCall=null;
    }

    /**
     * 获取点集以绘制调试
     * @private
     */
    getVerts(){
        this._verts.length=0;
        let inv=false;
        for(let i=-this._nU;i<=this._nU;i++){
            if(inv) {
                this._verts.push(new Vector3(i * UNIT, 0, -this._nV * UNIT));
                this._verts.push(new Vector3(i * UNIT, 0, this._nV * UNIT));
            }else{
                this._verts.push(new Vector3(i * UNIT, 0, this._nV * UNIT));
                this._verts.push(new Vector3(i * UNIT, 0, -this._nV * UNIT));
            }
            inv=!inv;
        }
        for(let i=-this._nV;i<=this._nV;i++){
            if(inv) {
                this._verts.push(new Vector3(-this._nU * UNIT, 0, i * UNIT));
                this._verts.push(new Vector3(this._nU * UNIT, 0, i * UNIT));
            }else{
                this._verts.push(new Vector3(this._nU * UNIT, 0, i * UNIT));
                this._verts.push(new Vector3(-this._nU * UNIT, 0, i * UNIT));
            }
            inv=!inv;
        }
    }
}